package cn.mengfly.algorithm.search;

import cn.mengfly.algorithm.util.ArrayUtil;

/**
 * Quick Union 算法
 *
 * @author wangp
 */
public class QuickUnionUf implements Uf {
    /**
     * 父连接数组，通过触点作为索引
     */
    private final int[] id;
    private int count;

    public QuickUnionUf(int n) {
        id = ArrayUtil.range(n);
        count = n;
    }


    @Override
    public void union(int p, int q) {
        int pNum = find(p);
        int qNum = find(q);

        if (pNum == qNum) {
            return;
        }

        id[qNum] = pNum;
        count--;
    }

    @Override
    public int find(int p) {
        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }

    @Override
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public int count() {
        return count;
    }
}
